class Solution
{
    int h[1010], ne[2010], e[2010], idx = 0;
    bool st[1010];
public:
    void add(int a, int b)
    {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges)
    {
        vector<int> ans;
        int n = edges.size();
        for (int i = 0; i < n; i++)
        {
            memset(h, -1, sizeof(h));
            memset(ne, 0, sizeof(ne));
            memset(e, 0, sizeof(e));
            memset(st, false, sizeof(st));

            idx = 0;

            for (int j = 0; j < n; j++)
            {
                if (i == j) continue;

                int a = edges[j][0], b = edges[j][1];
                add(a, b), add(b, a);
            }

            queue<int> q;
            q.push(1);
            st[1];
            while (!q.empty())
            {
                int t = q.front();
                q.pop();
                for (int j = h[t]; j != -1; j = ne[j])
                {
                    int k = e[j];
                    if (!st[k])
                    {
                        st[k] = true;
                        q.push(k);
                    }
                }
            }

            bool flag = true;
            for (int j = 1; j <= n; j++)
            {
                if (!st[j])
                {
                    flag = false;
                    break;
                }
            }
            if (flag) ans = edges[i];
        }
        return ans;
    }
};